package com.cuz.daileetcode.treedp;

import com.cuz.daileetcode.utils.TreeNode;

/**
 * @author cuzz
 * @version 1.0
 * @description: 见【树形dp：二叉树的最大距离】
 * @date 13:25 2022/1/2
 **/
public class TreeMaxDistance {


    private static class SubTreeInfo {
        int maxDistance;
        int height;

        public SubTreeInfo(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }


    public static int getMaxDistanceOf(TreeNode root) {
        return recursionGetSubTreeInfo(root).maxDistance;
    }

    private static SubTreeInfo recursionGetSubTreeInfo(TreeNode nowNode) {
        //如果当前节点是叶子节点
        if (nowNode == null) {
            //叶子节点最大距离0，高度0
            return new SubTreeInfo(0, 0);
        }
        //左子树的信息
        SubTreeInfo leftSubTreeInfo = recursionGetSubTreeInfo(nowNode.left);
        //右子树信息
        SubTreeInfo rightSubTreeInfo = recursionGetSubTreeInfo(nowNode.right);
        //当前节点作为根节点的树的高度 是左子树右子树高度max+1
        int nowNodeHeight = Math.max(leftSubTreeInfo.height, rightSubTreeInfo.height) + 1;
        //子树高度之和+1————————当前节点参与规则
        int subTreeHeightSumAdd1 = leftSubTreeInfo.height + rightSubTreeInfo.height + 1;
        //【三者最大值】
        int nowNodeMaxDistance = Math.max(
                //左右树最大距离max————————当前节点不参与规则
                Math.max(leftSubTreeInfo.maxDistance, rightSubTreeInfo.maxDistance),
                //子树高度之和+1
                subTreeHeightSumAdd1);
        //返回当前树的信息
        return new SubTreeInfo(nowNodeMaxDistance, nowNodeHeight);
    }
}
